#
# @lc app=leetcode.cn id=117 lang=python3
#
# [117] 填充每个节点的下一个右侧节点指针 II
#
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
# @lc code=start
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return None
        self.nextStart = None
        self.last = None
        start = root
        while start:
            self.last = None
            self.nextStart = None
            while start:
                if start.left:
                    self.handle(start.left)
                if start.right:
                    self.handle(start.right)
                start = start.next
            start = self.nextStart
        return root
    
    def handle(self, node):
        if self.last is not None:
            self.last.next = node
        if self.nextStart is None:
            self.nextStart = node
        self.last = node

# @lc code=end

